package 动态规划.状态压缩dp;

/**
 * @author aodre , QQ : 480029069
 * @date 2022/12/22 13:21
 */
public class leetcode1799最大分数和 {
    /*
      这个题是真的烦
      这个枚举的过程有点小迷糊！
     */

    /*
      另外的一种暴力递归的 想法
      这个枚举的方式是值得深思的说实话！
      又解锁了一种新的方式
      关键的问题在于这里的 flag 数组是个变量，在暴力递归中已经超越了整形的 范围了
     */
    public int recursion(int n,int nums[],boolean flag[],int len){
        if(n == 0)
            return 0;
        int ans = 0;
        for(int i = 0;i < len;i++){
            if(flag[i])
                continue;
            flag[i] = true;
            for(int j = i + 1;j < len;j++){
                if(flag[j])
                    continue;
                flag[j] = true;
                ans = Math.max(ans,recursion(n - 1,nums,flag,len) + n * gcd(nums[i],nums[j]));
                flag[j] = false;
            }
             flag[i] = false;
        }
        return  ans;
    }
    public static  int gcd(int a,int b){
        return b == 0 ? a : gcd(b,a % b);
    }

    /*
    上面的代码不变
    就是提供一种新的 思路，直接在 nums[] 数组上面动手脚,可以直接省掉 flag[]
    这样写怎么 记忆化搜索 ??
    假设这个缓存表可以这样声明, Map<Integer,int[]> dp  这样声明怎么写?
     */
    public int recursion(int n,int nums[]){
        if(n == 0)
            return 0;
        int ans = 0;
        for(int i = 0;i < nums.length;i++){
            //  - 1标志当前 nums[i] 已经用过不能再用了
            if(nums[i] == -1)
                continue;
            int cur1 = nums[i];
            nums[i] = -1;
            for(int j = i + 1;j < nums.length;j++){
                if(nums[j] == -1)
                    continue;
                int cur2 = nums[j];
                nums[j] = -1;
                ans = Math.max(ans,recursion(n - 1,nums) + n * gcd(cur1,cur2));
                nums[j] = cur2;
            }
            nums[i] = cur1;
        }
        return ans;
    }

    /*
      来 状态压缩
      注意 一下 这个 和 CanIWin 的一些 区别， CanIwin 是 一次 在 一个 范围 内 选一个数 （选过不能选了） 一层for
      而这个题 是一次选两个 数 两层 for
      这说明了什么
      体会一下；
     */
    public int recursion(int n,int nums[],int status){
        if(n == 0)
            return 0;

        int ans = 0;
        for(int i = 0;i < nums.length;i++) {
            if ((status & (1 << i)) != 0)
                continue;
            for (int j = i + 1; j < nums.length; j++) {
                if ((status & (1 << j)) != 0)
                    continue;
                ans = Math.max(ans, recursion(n - 1, nums, status | (1 << i) | (1 << j)) + n * gcd(nums[i],nums[j]));
            }
        }
        return ans;
    }

    /*
     记忆化搜索
     写出来 有点生疏的
     这个题 中 dp 表不需要做什么 初始值
     dp = 0 就是 没算过，因为算过的话  ，值不会是 0
     这个题的 结果的特殊性，
     算过。没算过的 这种判断也 挺细节的！
     */
    public int solution(int nums[]){
        int n = nums.length >> 1;
        int dp [][]  = new int[1 << nums.length][n + 1];
        return recursion(n,nums,0,dp);
    }
    public int recursion(int n,int nums[],int status,int dp[][]){
        if(n == 0)
            return dp[status][n] = 0;
        if(dp[status][n] != 0)
            return dp[status][0];
        int ans = 0;
        for(int i = 0;i < nums.length;i++) {
            if ((status & (1 << i)) != 0)
                continue;
            for (int j = i + 1; j < nums.length; j++) {
                if ((status & (1 << j)) != 0)
                    continue;
                ans = Math.max(ans, recursion(n - 1, nums, status | (1 << i) | (1 << j),dp) + n * gcd(nums[i],nums[j]));
            }
        }
        return dp[status][n] = ans;
    }
}
